1. Field of the Invention
The present invention concerns communication systems in which, in order to improve the fidelity of the transmission, the data to be transmitted are subjected to a channel encoding. It concerns more particularly a decoding method, as well as the devices and apparatus adapted to implement this method.
2. Description of the Related Art
It will be recalled that so-called “channel” encoding consists, when the “codewords” sent to the receiver are formed, of introducing a certain amount of redundancy in the data to be transmitted. More particularly, by means of each codeword, a predetermined number k of information symbols are transmitted which are chosen from a predetermined “alphabet” of finite size; to these k information symbols are added a number (n−k) of so-called “parity” symbols, taken from the same alphabet, so as to form codewords of length n; the set rules for calculation of the parity symbols as a function of information symbols defines a “code”, or “encoding method”, of parameters (n,k).
At the receiver, the associated decoding method then judiciously uses this redundancy to detect any transmission errors and if possible to correct them. More particularly, the decoding is carried out in two main steps.
The first step consists of associating an “associated codeword” with the received word. To do this, the decoder first analyzes the received word to verify whether it belongs to the code. If that is the case, it is assumed that no transmission error has occurred, and said “associated codeword” will simply be identical to the received word. If that is not the case, it is thereby deduced that some symbols in the received word are erroneous, and a correction algorithm is then implemented which is adapted to replace some of the received symbols with other symbols of the same alphabet, such that the result is a codeword, which will then constitute said “associated codeword”.
The second step simply consists in reversing the encoding method, that is to say in removing the redundant symbols from the “associated codeword” to retrieve the initial data.
More particularly, the invention concerns the first of these two steps and the conditions for implementation of said correction algorithms. The role of these is usually to associate with the received word the codeword situated at the shortest Hamming distance from this received word, the “Hamming distance” being, by definition, the number of places where two words of the same length have a different symbol. Each code thus provides an error correction capacity which is limited by the smallest Hamming distance between any two words of the code, which is referred to as the “minimum distance” of the code d; more specifically, when the chosen correction algorithm is required to find the position of possible errors in any received word, and to provide a replacement symbol for each of these positions, the capacity to correct at best INT[(d−1)/2] errors can be ensured for a code of minimum distance d (“INT” designates the integer part); if the received word contains a number of errors strictly greater than INT[(d−1)/2], the algorithm will in certain cases be able to propose a correction, but it will then of course be very uncertain that this correction will be the right one, that is to say that the associated codeword is really the codeword sent by the transmitter.
Certain of the encoding methods typically used, for example in CD (compact disc) and DVD (digital video disc) recordings, are “product codes”. In these methods, the symbols of each codeword may be placed in a table comprising n1 rows and n2 columns, such that the symbols constituting each row form a word belonging to a first “component” code (n1,k1), and the symbols constituting each column form a word belonging to a second component code (n2,k2). It is easy to understand that such product codes are advantageous: for example, if it is found that in a received word, a certain row does not belong to the first code and a certain column does not belong to the second code, it is immediately deduced from this, on the assumption that a single received symbol is tainted by error, that this erroneous symbol is situated at the crossing point of said row and said column. Another great advantage is that correction of all the errors of the received word may be achieved even if it may be initially impossible to correct certain of its rows with the algorithm associated with the first code, and/or initially impossible to correct certain of its columns with the algorithm associated with the second code. this is because the iterative correction of the rows one after the other, then of the columns one after the other, then the rows again, and so forth as necessary, may very well succeed in progressively reducing the number of errors, such that, at a certain stage, this number may fall in each row within the correction capacity of the first algorithm and in each column within the correction capacity of the second algorithm.
U.S. Pat. Nos. 6,047,395 and 6,138,263, for example, disclose methods of decoding a product code. These methods comprise a step consisting, when the first (respectively second) algorithm is unable to propose a correction for a row (respectively column) under consideration, of “erasing” the whole of said row (respectively column): this means that, when it is then sought to correct the columns (respectively rows), the positions whose symbols have been “erased” are signaled to the second (respectively first) algorithm. This is because, in general terms, when an algorithm has to correct a word (in the present case a row or column), the fact of knowing in advance the positions containing doubtful symbols considerably facilitates the algorithm's task; more particularly, it is known that an algorithm capable of taking this information into account has, if only words comprising erasures are submitted to it, a reliable correction limit twice that which it has if only words containing errors of unknown position are submitted to it. These methods of decoding product codes with erasure of uncorrectable rows and columns thus makes it possible both to tolerate a greater number of transmission errors, and to accelerate the correction procedure of these errors.
Even though such decoding methods have certain advantages, they have the drawback of giving rise to a relatively high rate of false corrections. This is because each time a row or column is erased, any information about the word which could have remained in that row or that column despite the transmission errors which that row or column has undergone, is of course lost. Consequently, if it is nevertheless desired to achieve true correction of this word, it is necessary to have a sufficient number of reliable symbols in the positions not erased of the table. However, the fact of accepting the “correction” supplied by the algorithms each time they are able to supply a “correction” means that often, when the number of errors in a row or column submitted to the row or column algorithm is relatively high, a new row or column will be entered, which is in fact tainted with errors (without this having been realized), due to the fact that the algorithm was able to propose an apparently corrected word by modifying a relatively small number of symbols, of which at least one was correct. An increasing number of false symbols will thus be generated during the subsequent steps of “correcting” this word, and in these circumstances, a highly erroneous “associated codeword” will generally result.